package 中等.其他;

/**
 * 给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
 * left 中的每个元素都小于或等于 right 中的每个元素。
 * left 和 right 都是非空的。
 * left 的长度要尽可能小。
 * 在完成这样的分组后返回 left 的 长度 。
 * 用例可以保证存在这样的划分方法。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals
 */
public class 分割数组_915 {

    public static void main(String[] args) {

    }

    /**
     * 两次遍历
     * left 的最大值必须 <= right 的最小值
     *
     * @param nums
     * @return
     */
    public int partitionDisjoint(int[] nums) {
        // [i,nums.length-1] 中的最小值
        int[] rightMin = new int[nums.length];
        rightMin[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
        }

        int leftMax = nums[0];
        for (int i = 0; i < nums.length; i++) {
            leftMax = Math.max(nums[i], leftMax);
            if (leftMax <= rightMin[i + 1]) {
                return i + 1;
            }
        }

        return 0;
    }

}
